package com.leetcode.algorithm.y22.m06;

/**
 * 45. 跳跃游戏 II
 * 
 * https://leetcode.cn/problems/jump-game-ii/
 * 
 * @author jie.deng
 *
 */
class Question0045Solution01 {

	public int jump(int[] nums) {
		int len = nums.length;
		// DP状态定义：dp[i]表示到达第i个下标最少的跳跃次数
		int[] dp = new int[len];

		// 状态初始化
		dp[0] = 0;

		for (int i = 1; i < len; i++) {
			dp[i] = Integer.MAX_VALUE;
			// 第i个下标由之前的第i-1、i-2、...0个下标跳跃而来
			for (int j = i - 1; j >= 0; j--) {
				if (dp[j] != Integer.MAX_VALUE && j + nums[j] >= i) {// dp[j] == Integer.MAX_VALUE表示第j个下标不可达
					dp[i] = Math.min(dp[i], dp[j] + 1);
				}
			}
		}
		return dp[len - 1];
	}

}